1. Field of the Invention
The present invention relates to a method of back-tracking to be performed by a computer, operating under commands of a program usually written in a logic type language such as PROLOG.
2. Description of the Background Art
Under a program written in a logic type language such as PROLOG, a computer is required to be capable of performing a process called back-tracking, in which an execution of an alternative predicate is automatically attempted in a case of a failure of an execution of a certain predicate.
Namely, as in an exemplary program of FIG. 1(A) which commands performing of the sequence of processes illustrated in FIG. 1(B), when there are two admissible clauses "b, !, c, d" and "e, f" for a certain predicate "a" to be executed, i.e., the predicate "a" is executable if one or the other of these possibilities "b, !, c, d" and "e, f" can successfully be executed, the first one "b, !, c, d" will be attempted first, and only when the execution of this first one "b, !, c, d" has failed, an attempt is automatically made for an execution of another alternative one "e, f". Here, in attempting the execution of the alternative one "e, f", it is necessary to restore initial conditions used in the abortive attempt for the execution of the first one "b, !, c, d", in order to maintain consistency.
Conventionally, for the purpose of assisting a programmer in handling such back-tracking processes effectively, there is provided a back-track controlling means which enable the programmer to explicitly control the performance of the back-tracking processes, within the framework of logic type languages. Such a back-tracking control means is often called an operator, among which a most notable example being a cut operator in PROLOG.
In the example of FIG. 1 (A) above, there is a cut operator "!" which will be carried out after the successful execution of the predicate "b". This cut operator functions such that when the process reaches this cut operator "!", the back-tracking of the predicate "a" will not take place any more. Thus, when the execution of the predicate "b" fails in the attempt to perform the first clause "b, !, c, d", the back-tracking to the alternative clause "e, f" will be performed as the failure of the execution of the predicate "b" occurs before the cut operator "!" is reached, as indicated by a dashed line in FIG. 1(B), whereas when the execution of the predicate "c" fails, the back-tracking will not be performed as this failure of executing the predicate "c" occurred after the cut operator "!" has been reached, so that the failure of the execution of the predicate "a" will be confirmed at this point, without attempting the alternative clause "e, f". The process may then go back further to a superior predicate preceding the predicate "a" for which the predicate "a" is a part of an admissible clause.
However, conventionally, such a back-track controlling means is actually realized by a computer in essentially a single manner, so that it has not been possible to provide the programmer with a number of different types of such back-track controlling means, from which a suitable one can freely be selected in accordance with the need of the programmer. As a consequence, the programming in a logic type language has been very inflexible as far as the back-track controlling means is concerned, such that in order to facilitate sufficient handling of the back-tracking, a highly skillful programming has been indispensable, which subsequently complicates the program itself, in which case the debugging is more difficult and running time becomes longer.